#include "header.h"

int* merge_arrays(int a[1024], int b[], int n1, int n2)
{//Merges two arrays and sorts while merging.
	int* c;
	int i=0;
	int counta=0, countb=0;
	if(n1+n2 ==0)
	{
		c = (int*)malloc(sizeof(int)*1);
		c[0] = 1001;
		return c;
	}
	if(n2==0)
	{
		c = (int*)malloc(sizeof(int)*n1);
		for(i=0;i<n1;i++)
			c[i] = a[i];
		return c;
	}
	else
		c = (int*)malloc(sizeof(int)*(n1+n2));

	for(i=0;i<(n1+n2);i++)
	{
		if(counta<n1&&countb<n2)
		{
			if(a[counta]<b[countb])
				c[i] = a[counta++];
			else if(a[counta]>=b[countb])
				c[i] = b[countb++];
		}
		else if(counta>=n1)
			c[i] = b[countb++];
		else if(countb>=n2)
			c[i] = a[counta++];
		else
			printf("ERROR");
	}
	return c;
}

int** merge(int a[1024][1024], int start, int end, int numrow)
{	//Loops through the rows of the matrix and merges them up until we finally get a 1,000,000 matrix
	int i=0, j=0;
	int** arrayaddress;
	int loop=0;
	int path = 0, path2=0;
	arrayaddress = (int**)malloc(sizeof(int*)*1024);


	for(i=0;i<512;i++)
	{//First Loop
		if(i<500)
		{
			arrayaddress[i] = merge_arrays(a[i*2],a[i*2+1],1000, 1000);
			size[i] = 2000;
		}
		else if(i>=500)
		{
			arrayaddress[i] = (int*)malloc(sizeof(int)*1);
			arrayaddress[i][0] = 1001;
			size[i] = 0;
		}
	}
	path = 512;
	for(i=1;i<=9;i++)
	{//Second to tenth loop -> 2^10
		loop = power(2,9-i);
		for(j=0;j<loop;j++)
		{
			arrayaddress[j+path] = merge_arrays(arrayaddress[j*2+path2],arrayaddress[j*2+1+path2],size[j*2+path2],size[j*2+path2+1]);
			size[j+path] = size[j*2+path2] + size[j*2+path2+1];
		}
		path2 = path;
		path+=loop;

	}
	return arrayaddress;
}
int** merge_thread(int a[1024][1024], int*** tableaddress, int start, int end, int numrow)
{	//same as the merge() but this one is a subversion(used for threading)
	int i=0, j=0;
	int** arrayaddress;
	int interval[10] = { 512, 256, 128, 64, 32, 16, 8, 4, 2, 1};
	int loop=0, reps=1;
	int path = 0, path2=0;
	arrayaddress = *tableaddress;	//To ease using the triple pointer.
	for(i=start;i<end+1;i=i+2)
	{//First Loop
		if(i<999)
		{
			arrayaddress[i/2] = merge_arrays(a[i],a[i+1],1000, 1000);
		}
		else
		{
			arrayaddress[i/2] = (int*)malloc(sizeof(int)*1);
			arrayaddress[i/2][0] = 1001;

		}
	}
	while(numrow!=power(2,reps))
	{
		reps++;
	}
	path=512;
	loop = numrow/2;
	for(i=1;i<=reps;i++)
	{//Second to tenth loop -> 2^10
		j=0;
		loop/=2;
		for(j=0;j<loop;j++)
		{
			arrayaddress[j+path+start/power(2,i+1)] = merge_arrays(arrayaddress[start/power(2,i)+j*2+path2],arrayaddress[start/power(2,i)+j*2+1+path2],size[start/power(2,i)+j*2+path2],size[start/power(2,i)+j*2+1+path2]);
		}
		path2=path;
		path += interval[i];
	}
	return arrayaddress;
}

int power(int a, int b)
{
	//return value of a^b
	int i=0;
	int value = 1;
	for(i=0;i<b;i++)
	{
		value*=a;
	}

	return value;
}
